# 面试题 04.06 中等： 后继者

# Definition for a binary tree node.
# class HOT.TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    l = []

    def inorderSuccessor(self, root: HOT.TreeNode, p: HOT.TreeNode) -> HOT.TreeNode:

        def midSort(cur):

            if cur == None:
                return

            midSort(cur.left)
            self.l.append(cur)
            midSort(cur.right)

        midSort(root)
        # print(self.l)
        if self.l.index(p) == len(self.l) - 1:
            return None
        return self.l[(self.l.index(p) + 1)]
